class Book:
    def __init__(self, id, title, author, category=None):
        self.id = id
        self.title = title
        self.author = author
        self.category = category

    def __str__(self):
        return f"ID: {self.id}, Title: {self.title}, Author: {self.author}, Category: {self.category}"

class ListNode:
    def __init__(self, book=None):
        self.book = book
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert(self, book):
        new_node = ListNode(book)
        new_node.next = self.head
        self.head = new_node

    def delete(self, id):
        current = self.head
        previous = None
        while current is not None and current.book.id != id:
            previous = current
            current = current.next
        if current is None:
            return False
        if previous is None:
            self.head = current.next
        else:
            previous.next = current.next
        return True

    def find(self, id):
        current = self.head
        while current is not None:
            if current.book.id == id:
                return current.book
            current = current.next
        return None

    def update(self, id, title=None, author=None, category=None):
        current = self.head
        while current is not None:
            if current.book.id == id:
                if title:
                    current.book.title = title
                if author:
                    current.book.author = author
                if category:
                    current.book.category = category
                return True
            current = current.next
        return False

    def display(self):
        current = self.head
        while current is not None:
            print(current.book)
            current = current.next

class HashTable:
    def __init__(self, size=20):
        self.table = [None] * size

    def hash_function(self, key):
        return key % len(self.table)

    def insert(self, book):
        index = self.hash_function(book.id)
        if self.table[index] is None:
            self.table[index] = LinkedList()
        self.table[index].insert(book)

    def delete(self, id):
        index = self.hash_function(id)
        if self.table[index] is not None:
            return self.table[index].delete(id)
        return False

    def find(self, id):
        index = self.hash_function(id)
        if self.table[index] is not None:
            return self.table[index].find(id)
        return None

    def update(self, id, title=None, author=None, category=None):
        index = self.hash_function(id)
        if self.table[index] is not None:
            return self.table[index].update(id, title, author, category)
        return False

    def display(self):
        for linked_list in self.table:
            if linked_list is not None:
                linked_list.display()

class BinarySearchTree:
    class Node:
        def __init__(self, category):
            self.category = category
            self.books = LinkedList()
            self.left = None
            self.right = None

    def __init__(self):
        self.root = None

    def insert(self, category):
        self.root = self._insert(self.root, category)

    def _insert(self, node, category):
        if node is None:
            return self.Node(category)
        if category < node.category:
            node.left = self._insert(node.left, category)
        elif category > node.category:
            node.right = self._insert(node.right, category)
        return node

    def find(self, category):
        return self._find(self.root, category)

    def _find(self, node, category):
        if node is None:
            return None
        if category == node.category:
            return node
        elif category < node.category:
            return self._find(node.left, category)
        else:
            return self._find(node.right, category)

    def add_book_to_category(self, category, book):
        # 确保分类存在
        category_node = self.find(category)
        if category_node is None:
            self.insert(category)
            category_node = self.find(category)
        category_node.books.insert(book)

    def find_books_in_category(self, category):
        category_node = self.find(category)
        if category_node:
            print(f"分类 '{category}' 下的图书：")
            category_node.books.display()
        else:
            print(f"分类 '{category}' 下没有找到图书。")

# 菜单功能
def display_menu():
    print("欢迎使用图书管理系统")
    print("1. 添加图书")
    print("2. 删除图书")
    print("3. 查找图书")
    print("4. 修改图书信息")
    print("5. 显示所有图书")
    print("6. 添加图书分类")
    print("7. 查找分类下的图书")
    print("8. 退出系统")

def main():
    book_manager = HashTable()
    category_manager = BinarySearchTree()

    while True:
        display_menu()
        choice = input("请选择操作: ")

        if choice == '1':
            # 添加图书
            id = int(input("请输入图书ID: "))
            title = input("请输入图书标题: ")
            author = input("请输入图书作者: ")
            category = input("请输入图书分类（若暂无分类请输入'None'）: ")
            book = Book(id, title, author, category if category != 'None' else None)
            book_manager.insert(book)
            if category != 'None':
                category_manager.add_book_to_category(category, book)
            print("图书添加成功。")

        elif choice == '2':
            # 删除图书
            id = int(input("请输入要删除的图书ID: "))
            if book_manager.delete(id):
                print("图书删除成功。")
            else:
                print("图书删除失败，未找到对应ID的图书。")

        elif choice == '3':
            # 查找图书
            id = int(input("请输入要查找的图书ID: "))
            book = book_manager.find(id)
            if book:
                print(f"找到图书：{book}")
            else:
                print("未找到对应ID的图书。")

        elif choice == '4':
            # 修改图书信息
            id = int(input("请输入要修改的图书ID: "))
            title = input("请输入新的图书标题（留空保持不变）: ")
            author = input("请输入新的图书作者（留空保持不变）: ")
            category = input("请输入新的图书分类（留空保持不变）: ")
            if book_manager.update(id, title if title else None, author if author else None, category if category else None):
                print("图书信息更新成功。")
            else:
                print("图书信息更新失败，未找到对应ID的图书。")

        elif choice == '5':
            # 显示所有图书
            print("所有图书信息如下：")
            book_manager.display()

        elif choice == '6':
            # 添加图书分类
            category = input("请输入新的图书分类名称: ")
            category_manager.insert(category)
            print("图书分类添加成功。")

        elif choice == '7':
            # 查找分类下的图书
            category = input("请输入要查找的图书分类名称: ")
            category_manager.find_books_in_category(category)
            #print(f"分类 '{category}' 下的图书如下：")
            #category_manager.find_books_in_category(category)

        elif choice == '8':
            print("感谢使用图书管理系统，再见！")
            break

        else:
            print("无效的输入，请重新输入。")

if __name__ == "__main__":
    main()
